package com.blah.gwtgames.client.common.dlx;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class DancingLinks
{
	private Constraint root = new Constraint();
	private List constraints = new ArrayList();
	private Map choices = new HashMap();
	private Stack chosen = new Stack();
	private boolean canHalt = false;
	private boolean halt = false;
	
	public DancingLinks()
	{
		constraints.add(root);
	}
	
	public void addConstraint(Constraint constraint)
	{
		if (constraint.constraint != null)
			throw new IllegalArgumentException("Constraint already in use.");
		
		constraint.constraint = root;
		constraint.index = constraints.size();
		constraints.add(constraint);
		
		constraint.left = root.left;
		constraint.right = root;
		root.left.right = constraint;
		root.left = constraint;
	}
	
	public void addChoice(Choice choice)
	{
		if (choice.nodes.isEmpty())
			throw new IllegalArgumentException("Choice has no constraints.");
		
		choices.put(choice.getKey(), choice);
		
		Collections.sort(choice.nodes, new Comparator()
		{

			public int compare(Object arg0, Object arg1)
			{
				Node node0 = (Node)arg0;
				Node node1 = (Node)arg1;
				
				if (node0.constraint == null ||
					node0.constraint.constraint != root ||
					node1.constraint == null ||
					node1.constraint.constraint != root)
					throw new ClassCastException("Some Constraints in this Choice do not belong to this DancingLinks.");
				
				return node1.constraint.index - node0.constraint.index;
			}
			
		});
		
		Iterator iterator = choice.nodes.iterator();
		while (iterator.hasNext())
		{
			Node node = (Node) iterator.next();
			
			node.down = node.constraint;
			node.up = node.constraint.up;
			node.up.down = node;
			node.constraint.up = node;
			node.constraint.size++;
			
			node.left = choice.root.left;
			node.right = choice.root;
			choice.root.left.right = node;
			choice.root.left = node;
		}
		
		choice.root.constraint = root;
	}
	
	public void choose(Object key)
	{
		if (!choices.containsKey(key))
			throw new IllegalStateException("No choice with the given key exists.");
		
		choose((Choice)choices.get(key));
	}
	
	public void choose(Choice choice)
	{
		for (Node node = choice.root.right; node != choice.root; node = node.right)
		{
			if (node.constraint.covered)
			{
				throw new IllegalStateException("Choice breaks some constraints.");
			}
		}
		
		chosen.push(choice);
		for (Node node = choice.root.right; node != choice.root; node = node.right)
		{
			coverConstraint(node.constraint);
		}
	}
	
	public boolean canUndo()
	{
		return !chosen.empty();
	}
	
	public Choice undo()
	{
		if (chosen.empty())
			throw new IllegalStateException("Cannot undo.");
		
		Choice choice = (Choice)chosen.pop();
		for (Node node = choice.root.left; node != choice.root; node = node.left)
		{
			uncoverConstraint(node.constraint);
		}
		
		return choice;
	}
		
	public void solve(SolvedCallback callback)
	{
		solve(new HashSet(), callback);
		halt = false;
	}
	
	protected void solve(Set choices, SolvedCallback callback)
	{
		if (root.left == root)
		{
			canHalt = true;
			callback.solved(choices);
			canHalt = false;
			return;
		}
		
		int lowestValue = Integer.MAX_VALUE;
		Constraint constraint = null;
		for (Constraint c = (Constraint) root.right; c != root; c = (Constraint) c.right)
		{
			if (c.size < lowestValue)
			{
				constraint = c;
				lowestValue = constraint.size;
			}
		}
		
		if (constraint.size == 0)
			return;
		
		coverConstraint(constraint);
		for (Node row = constraint.down; row != constraint; row = row.down)
		{
			for (Node node = row.right; node != row; node = node.right)
			{
				coverConstraint(node.constraint);
			}
			
			choices.add(row.choice);
			solve(choices, callback);
			choices.remove(row.choice);
			
			for (Node node = row.left; node != row; node = node.left)
			{
				uncoverConstraint(node.constraint);
			}
			
			if (halt)
				break;
		}
		uncoverConstraint(constraint);
	}
	
	public void halt()
	{
		if (!canHalt)
			throw new IllegalStateException("Can't halt; algorithm isn't running.");
		
		halt = true;
	}
	
	protected void coverConstraint(Constraint constraint)
	{
		if (constraint == root)
			return;
		
		constraint.covered = true;
		
		constraint.left.right = constraint.right;
		constraint.right.left = constraint.left;
		
		for (Node i = constraint.down; i != constraint; i = i.down)
		{
			for (Node j = i.right; j != i; j = j.right)
			{
				j.up.down = j.down;
				j.down.up = j.up;
				j.constraint.size--;
			}
		}
	}
	
	protected void uncoverConstraint(Constraint constraint)
	{
		if (constraint == root)
			return;
		
		constraint.covered = false;
		
		for (Node i = constraint.up; i != constraint; i = i.up)
		{
			for (Node j = i.left; j != i; j = j.left)
			{
				j.up.down = j;
				j.down.up = j;
				j.constraint.size++;
			}
		}
		
		constraint.left.right = constraint;
		constraint.right.left = constraint;
	}
}
